#include "doublelink.h"
#include <iostream>
#include <climits>
Doublelink::Doublelink() : size(0)
{
    head = new Node(0);
    tail = head;
}

void Doublelink::InsertTail(const ElementType &element)
{

    tail->next = new Node(element);
    tail->next->prev = tail;
    tail = tail->next;
    size++;
}

void Doublelink::show()
{
    Node *travePoint = head->next; // 存有效数据的第一个节点
    while (travePoint != nullptr)
    {
        std::cout << travePoint->value << " "; // 打印数据域
        travePoint = travePoint->next;
    }
    std::cout << std::endl;
}

void Doublelink::ReserveShow()
{
    Node *travePoint = tail; // 存有效数据的第一个节点
    while (travePoint != head)
    {
        std::cout << travePoint->value << " "; // 打印数据域
        travePoint = travePoint->prev;
    }
    std::cout << std::endl;
}

void Doublelink::InsertHead(const ElementType &element)
{
    Node *newnode = new Node(element);
    newnode->next = head->next;
    newnode->prev = head;
    head->next = newnode;
    if (size != 0)
        newnode->next->prev = newnode;
    else
        tail = newnode;
    size++;
}

size_t Doublelink::Size()
{
    return size;
}

void Doublelink::RemoveByIndex(int index)
{
    if (index < 0 || index >= size)
    {
        return;
    }
    Node *TP = head;
    for (int i = 0; i < index; i++)
    {
        TP = TP->next;
    }
    Node *freeNode = TP->next;
    TP->next = freeNode->next;
    if (freeNode == tail)
    {
        tail = tail->prev;
    }
    else
    {
        freeNode->next->prev = TP;
    }
    delete freeNode;
    size--;
}

void Doublelink::InsertByIndex(int index, const ElementType &element)
{

    if (index < 0 || index >= size)
    {
        return;
    }
    Node *TP = head;
    for (int i = 0; i < index; i++)
    {
        TP = TP->next;
    }
    Node *newNode = new Node(element);
    newNode->next = TP->next;
    newNode->prev = TP;
    TP->next = newNode;
    newNode->next->prev = newNode;
    size++;
}

void Doublelink::RemoveByElement(const ElementType &element)
{
    Node *TP = head->next;
    while (TP != nullptr)
    {

        if (TP->value == element)
        {
            if (TP->next != nullptr)
            {
                TP->prev->next = TP->next;
                TP->next->prev = TP->prev;
                delete TP;
                size--;
            }
            else
            {
                TP->prev->next = nullptr;
                delete TP;
                size--;
            }
        }
        TP = TP->next;
    }
}

void Doublelink::UpdateByElement(const ElementType &oldv, const ElementType &newv)
{

    Node *TP = head->next;
    while (TP != nullptr)
    {

        if (TP->value == oldv)
        {
            TP->value = newv;
        }
        TP = TP->next;
    }
}

ElementType &Doublelink::operator[](int index)
{
    Node*TP=head->next;
    for (int i = 0; i <index; i++)
    {
        TP=TP->next;

    }
    return TP->value;

}

size_t Doublelink::FindByElement(const ElementType &element)
{
    Node*TP=head->next;
    
    for (size_t i = 0; i <size; i++)
    {   
        if (TP->value==element)
        {
            return i;
        }
        TP=TP->next;

    }
    return ULONG_MAX;
}

void Doublelink::FastSort()
{

    FastSort1(head->next,nullptr);

}

Doublelink Doublelink::Merge(const Doublelink &link)
{
    Doublelink result;
    Node *p1 = head->next;
    Node *p2 = link.head->next;
    while (p1 && p2)
    {
        if (p1->value > p2->value)
        {
            result.InsertTail(p2->value);
            p2 = p2->next;
        }
        else
        {

            result.InsertTail(p1->value);
            p1 = p1->next;
        }
    }
    while (p1)
    {
        result.InsertTail(p1->value);
        p1 = p1->next;
    }
    while (p2)
    {
        result.InsertTail(p2->value);
        p2 = p2->next;
    }

    return result;



}

void Doublelink::FastSort1(Node *start, Node *end)
{
    // if (start==end)
    // {
    //     return;
    // }
    // Node*temp=start;
    // Node*left=start;
    // Node*right=end;
    // static int intleft=0;
    // static int intright=size-1;
    // while (intleft<intright)
    // {   
    // while (right->value> temp->value)
    // {   intright--;
    //     right=right->prev;
    // }
    // if (intleft<intright)
    // {
    // left->value=right->value;
    // left=left->next;
    // }
    
    // while (left->value<temp->value)
    // {   intleft++;
    //     left=left->next;
    // }
    // if (intleft<intright)
    // {
    // right->value=left->value;
    // right=right->prev;
    // }
    // }
    // left->value=temp->value;
    // FastSort1(start,left);
    // FastSort1(left->next,end);
      if (start==end)
    {
        return;
    }
    Node*temp=start;//基准值指针
    Node*slow=start;
    //快慢指针
    Node*fast=start->next;
    while (fast!=end)
    {
        //快指针所指的数据比基准值小
        if (fast->value<temp->value)
        {
            slow=slow->next;
            std::swap(fast->value,slow->value);
        }
        fast=fast->next;

    }
    std::swap(slow->value,temp->value);
    FastSort1(start,slow);
    FastSort1(slow->next,end);
}
